package com.jzoffer;

public class TheNextPoint {
    public static void main(String[] args) {
        TreeLinkNode t1 = new TreeLinkNode(1);
        TreeLinkNode t2 = new TreeLinkNode(2);
        TreeLinkNode t3 = new TreeLinkNode(3);
        t1.left = t2;
        t1.right = t3;
        t2.next = t1;
        t3.next = t1;
        TreeLinkNode next = getNext(t2);
        System.out.println(next.val);
    }

    public static TreeLinkNode getNext(TreeLinkNode pNode){
        if(pNode == null){
            return pNode;
        }
        // No1 有右节点
        if(pNode.right != null){
            TreeLinkNode t = pNode.right;
            while (t.left  != null){
                t = t.left;
            }
            return t;
        }
        // No2 没有右结点 找父节点
        while (pNode.next != null){
            if(pNode.next.left == pNode){
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }
}

class TreeLinkNode{
    int val;
    TreeLinkNode left;
    TreeLinkNode right;
    // 父节点
    TreeLinkNode next;

    public TreeLinkNode(int val) {
        this.val = val;
    }
}
